package com.aikon.wht.paoshan.alg;

import java.util.Arrays;

import static com.aikon.wht.paoshan.PaoshanUtils.printArray;
import static com.aikon.wht.paoshan.PaoshanUtils.swap;


/**
 * @author WANGHAITAO273
 */
public class PaoshanOfSort {

    // 相等元素前后位置排序后不变为稳定排序，发生变化为不稳定排序
    // 稳定排序应用：一批订单按照金额从小到大排列，金额相同的订单，按照下单时间从早到晚排序。- 先按下单时间排序，再用稳定算法按照订单金额排序。稳定排序算法可以保持金额相同的两个订单，在排序后前后顺序不变
    // 原地排序：不需要额外存储空间的排序，空间复杂度低

    // 有序度是数组中具有有序关系的元素对的个数。有序元素对用数学表达式表示就是这样：有序元素对：a[i] <= a[j], 如果i < j。 逆有序度正好相反. 逆序元素对：a[i] > a[j], 如果i < j。
    // 满有序度=有序度+逆序度=n*(n-1)/2 例如数组{4,5,6,3,2,1} 满有序度=6*5/2=15 有序度=(4,5 4,6 5,6)=3 逆有序度=(4,3 4,2 4,1 5,3 5,2 5,1 6,3 6,2 6,1 3,2 3,1 2,1)=12

    // 小规模排序：冒泡排序、插入排序、选择排序
    //
    //        是否原地排序  是否稳定排序  最好    最坏     平均
    // 冒泡   是            是           O(n)    O(n*n)   O(n*n)
    // 插入   是            是           O(n)    O(n*n)   O(n*n)
    // 选择   是            否           O(n*n)  O(n*n)   O(n*n)

    // 大规模排序：归并排序、快速排序 - 都是分治思想，类似编程技巧递归
    //

    /**
     * 冒泡排序
     * <p>
     * 冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。
     * 如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。
     * <p>
     * 1.冒泡排序是原地排序算法
     * 2.冒泡排序是稳定算法 - 只有交换才会改变位置，交换只发生在大小不等时
     * 3.冒泡排序的时间复杂度=O(n*n)
     * </p>
     * <p>
     * 对于包含 n 个数据的数组进行冒泡排序，平均交换次数是多少呢？最坏情况下，初始状态的有序度是 0，所以要进行 n*(n-1)/2 次交换。
     * 最好情况下，初始状态的有序度是 n*(n-1)/2，就不需要进行交换。我们可以取个中间值 n*(n-1)/4，来表示初始有序度既不是很高也不是很低的平均情况。
     * 换句话说，平均情况下，需要 n*(n-1)/4 次交换操作，比较操作肯定要比交换操作多，而复杂度的上限是 O(n*n)，所以平均情况下的时间复杂度就是 O(n*n)。
     * <p>
     * <p>
     * 4 5 6 3 2 1
     * 第一次冒泡   4 5 3 2 1 6
     * 第二次冒泡   4 3 2 1 5 6
     * 第三次冒泡   3 2 1 4 5 6
     * 第四次冒泡   2 1 3 4 5 6
     * 第五次冒泡   1 2 3 4 5 6
     * 第六次冒泡   1 2 3 4 5 6
     */
    public static class BubbleSort {
        public static int[] sort(int[] arr) {
            if (arr == null || arr.length == 0) {
                return arr;
            }
            for (int i = 0; i < arr.length; i++) {
                boolean swapped = false;
                for (int j = 0; j < arr.length - i - 1; j++) {
                    if (arr[j] > arr[j + 1]) {
                        int tmp = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = tmp;
                        swapped = true;
                    } else {

                    }
                }
                // 当某次冒泡操作已经没有数据交换时，说明已经达到完全有序，不用再继续执行后续的冒泡操作
                if (!swapped) {
                    break;
                }
            }

            return arr;
        }

        public static void main(String[] args) {
            printArray(sort(new int[]{4, 5, 6, 3, 2, 1}));
        }
    }

    /**
     * 插入排序
     * 插入排序也包含两种操作，一种是元素的比较，一种是元素的移动。
     * 当我们需要将一个数据 a 插入到已排序区间时，需要拿 a 与已排序区间的元素依次比较大小，找到合适的插入位置。
     * 找到插入点之后，我们还需要将插入点之后的元素顺序往后移动一位，这样才能腾出位置给元素 a 插入。
     * 首先，我们将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。
     * 插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。
     * <p>
     * <p>
     * 1.插入排序是原地排序
     * 2.插入排序是稳定排序
     * 3.插入排序时间复杂度=O(n*n)
     * <p>
     * 4 5 6 3 2 1
     * toInsert=5
     * 4 5 6 3 2 1
     * toInsert=6
     * 4 5 6 3 2 1
     * toInsert=3
     * 3 4 5 6 2 1
     * toInsert=2
     * 2 3 4 5 6 1
     * toInsert=1
     * 1 2 3 4 5 6
     */
    public static class InsertionSort {
        public static int[] sort(int[] arr) {
            // 未排区间从i开始
            for (int i = 1; i < arr.length; i++) {
                // 暂存要插入的未排数
                int toInsert = arr[i];
                int j = i - 1;
                // 已排区间从j开始
                while (j >= 0) {
                    if (toInsert < arr[j]) {
                        // 从左到由与已排区间依次比较，小于已排数则已排数右移一位
                        arr[j + 1] = arr[j];
                    } else {
                        break;
                    }
                    j--;
                }
                // 未排数插入右移后空出的已排区间
                arr[j + 1] = toInsert;
            }
            return arr;

        }

        public static void main(String[] args) {
            printArray(sort(new int[]{4, 5, 6, 3, 2, 1}));
        }

    }

    /**
     * 选择排序
     * 每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在已排序区间末尾，直到全部待排序的数据元素排完。
     * <p>
     * 1.选择排序是原地排序
     * 2.选择排序是不稳定的排序方法
     * 3.选择排序的时间复杂度是O(n*n)
     */
    public static class SelectionSort {
        public static int[] sort(int[] arr) {
            for (int i = 0; i < arr.length - 1; i++) {
                int j = i + 1;
                int minIndex = j;
                int min = arr[j];
                for (; j < arr.length; j++) {
                    if (arr[j] < min) {
                        min = arr[j];
                        minIndex = j;
                    }
                }
                // 交换待排区间最小值和已排区间末尾
                int tmp = arr[i];
                arr[i] = min;
                arr[minIndex] = tmp;

            }

            return arr;
        }

        public static void main(String[] args) {
            printArray(sort(new int[]{6, 3, 4, 5, 6, 1, 2, 7, 3, 2}));
        }
    }

    /**
     * 归并排序
     * 归并排序的核心思想还是蛮简单的。如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。
     * <p>
     * 1.递归排序不是原地排序算法 在任意时刻，CPU 只会有一个函数在执行，也就只会有一个临时的内存空间在使用。临时内存空间最大也不会超过 n 个数据的大小，所以空间复杂度是 O(n)。
     * 2.归并排序是稳定算法
     * 3.递归排序的时间复杂度=O(n*logn)
     * <p>
     * 时间复杂度计算：
     * T(n)=2*T(n/2)+n
     * =2*(2*T(n/4+n/2)+n = 4*T(n/4)+2*n
     * =4*(2*T(n/8)+n/4)+2*n = 8*T(n/8)+3*n
     * =2^k*T(n/2^k)+k*n
     * 当n/2^k=1时，k=logn,T(n)=n*T(1)+logn*n=n+n*logn
     * 所以时间复杂度=O(n*logn)
     */
    public static class RecursiveSort {
        public static int[] sort(int[] arr) {
            if (arr.length == 1) {
                return arr;
            }
            int mid = arr.length / 2;
            int[] arr1 = Arrays.copyOfRange(arr, 0, mid);
            int[] arr2 = Arrays.copyOfRange(arr, mid, arr.length);
            return merge(sort(arr1), sort(arr2));
        }

        private static int[] merge(int[] arr1, int[] arr2) {
            int[] ret = new int[arr1.length + arr2.length];
            int arr1Index = 0, arr2Index = 0;
            for (int i = 0; i < ret.length; i++) {
                if (arr1Index + arr2Index == ret.length) {
                    break;
                }
                if (arr1Index == arr1.length) {
                    ret[i] = arr2[arr2Index];
                    arr2Index++;
                } else if (arr2Index == arr2.length) {
                    ret[i] = arr1[arr1Index];
                    arr1Index++;
                } else if (arr1[arr1Index] < arr2[arr2Index]) {
                    ret[i] = arr1[arr1Index];
                    arr1Index++;
                } else {
                    ret[i] = arr2[arr2Index];
                    arr2Index++;
                }
            }
            return ret;
        }

        public static void main(String[] args) {
            printArray(sort(new int[]{54, 3, 32, 234, 134, 4, 556, 3, 2, 465, 23432423, 323, 235, 6, 4, 34, 4, 3, 1, 3, 4, 5, 44545, 4, 54}));
        }

    }

    /**
     * 快速排序
     * <p>
     * 分区+荷兰国旗问题（PaoshanOfNetherlandsFlag）
     * <p>
     * 1.快速排序是原地排序
     * 2.快速排序是非稳定排序 例如 1 3 3 4 2 根据末尾的2分区后两个3的前后位置变了
     * 3.快速排序的时间复杂度=O(n*logn)
     */
    public static class QuickSort {

        public static int[] sort(int[] arr) {
            return sort(arr, 0, arr.length - 1);
        }

        public static int[] sort(int[] arr, int start, int end) {
            if (end <= start) {
                return arr;
            }
            int less = start;
            int more = end;
            int current = start;
            int pivot = arr[end];
            while (current <= more) {
                if (arr[current] == pivot) {
                    current++;
                } else if (arr[current] < pivot) {
                    swap(arr, less, current);
                    less++;
                    current++;
                } else {
                    swap(arr, more, current);
                    more--;
                }
            }
            sort(arr, start, less - 1);
            sort(arr, more + 1, end);
            return arr;
        }


        public static void main(String[] args) {
            printArray(sort(new int[]{1, 3, 4, 6, 2, 3, 5, 6, 4, 7, 3}));
        }
    }


    /**
     * 堆排
     * <p>
     * 堆排序是原地排序
     * 时间复杂度O(N*logN)，额外空间复杂度O(1)
     * 堆结构非常重要
     * <p>
     * 1，堆结构的heapInsert与heapify
     * 2，堆结构的增大和减少
     * 3，如果只是建立堆的过程，时间复杂度为O(N)
     * 4，优先级队列结构，就是堆结构
     */
    public static class HeapSort {
        public static void heapSort(int[] arr) {
            if (arr == null || arr.length < 2) {
                return;
            }
            for (int i = 0; i < arr.length; i++) {
                heapInsert(arr, i);
            }
            int size = arr.length;
            swap(arr, 0, --size);
            while (size > 0) {
                heapify(arr, 0, size);
                swap(arr, 0, --size);
            }
        }

        public static void heapInsert(int[] arr, int index) {
            while (arr[index] > arr[(index - 1) / 2]) {
                swap(arr, index, (index - 1) / 2);
                index = (index - 1) / 2;
            }
        }

        public static void heapify(int[] arr, int index, int size) {
            int left = index * 2 + 1;
            while (left < size) {
                int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;
                largest = arr[largest] > arr[index] ? largest : index;
                if (largest == index) {
                    break;
                }
                swap(arr, largest, index);
                index = largest;
                left = index * 2 + 1;
            }
        }


        public static void main(String[] args) {
            int[] arr = {1, 34, 4, 5, 76, 8, 9};
            heapSort(arr);
            System.out.println(Arrays.toString(arr));
        }
    }

}